package leetcode_jz_offer.day8_dp;

/**
 * 求n的斐波那契数列
 **/
public class Num10I_斐波那契数列 {
    public int fib(int n) {
        final int MOD = 1000000007;//对大数进行取模操作，让结果不至于溢出
        if(n==0||n==1){
            return n;
        }
        if(n==2){
            return 1;
        }
        int first=1;
        int second=1;
        int third=1;
        while (n>2){
            third=first+second;
            third%=MOD;
            first=second;
            second=third;
            n--;
        }
        return third;
    }
}
